0%

【算法导论】二叉排序树

发表于 更新于
本文字数： 5.8k 阅读时长 ≈ 8 分钟

二叉排序树的性质：每个节点的左子树中的所有节点的关键字都小于该节点的关键值，而右子树中的所有节点的关键字都大于该节点的关键值。

二叉排序树的构造

二叉排序树的构造是指将一个给定的数据元素构造为相应的二叉排序树。

基本思想为：

对于任给的一组数据元素${ R1, R2, …, Rn } $, 可按以下方法来构造二叉排序树：

  1. 令$R1$为二叉树的根;

  2. 若$R2<R1$, 令$R2$为$R1$左子树的根结点，否则$R2$为$R1$右子树的根结点；

  3. 对$R3, …, Rn$结点，也是依次与前面生成的结点比较以确定输入结点的位置。

    这一方法中的一个结点插入，可用以下的非递归插入算法来实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**************************************\
函数功能：创建二叉排序树
输入：    原始数组
输出：    二叉排序树的根节点
\**************************************/
bstnode* CreatBst(int* arrayA,int n)
{
	bstnode *t,*s;
	t=NULL;
	for(int i=1;i<n;i++)
	{
		s=(bstnode*)malloc(sizeof(bstnode));
		s->key=arrayA[i];//从arrayA[1]开始
		s->lchild=s->rchild=NULL;
		t=InsertBst(t,s);//调用插入函数
	}
	return t;
}

二叉排序树的插入

插入过程可以由下图一目了然：

图1

从上述的插入过程可以看出每次插入的新结点都是二叉排序树的叶子结点并且不需移动其他结点，所以在进行插入这样的操作时比向量（线性表）操作更方便。由于对二叉排序树进行中序遍历时，可以得到一个按关键字大小排列的有序序列，所以对一个无序序列可通过构造二叉排序树和对这个排序树进行中序遍历来产生一个有序序列。

具体的程序实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**************************************\
函数功能：向二叉排序树中插入节点
输入：    二叉排序树的根节点、要插入的节点
输出：    二叉排序树的根节点
\**************************************/
bstnode* InsertBst(bstnode* t,bstnode* s)
{
	bstnode *f,*p;
	p=t;
	while(p!=NULL)
	{
		f=p;
	
		if(s->key<=p->key)
			p=p->lchild;
		else
			p=p->rchild;
	}
	if(t==NULL)
		return s;
	if(s->key<f->key)
		f->lchild=s;
	else
		f->rchild=s;
	return t;

}

二叉树的删除

若要删除的结点由p指出，双亲结点由q指出，则二叉排序树中结点的删除可分以下三种情况考虑：

  1. 若p指向叶子结点，则直接将该结点删除。

  2. 若p所指结点只有左子树pL或只有右子树pR，此时只要使pL或pR成为q所指结点的左子树或右子树即可，如下图(a)和(b)所示

  3. 若p所指结点的左子树pL和右子树pR均非空，则需要将pL和pR链接到合适的位置上，并且保持二叉排序树的特点，即应使中序遍历该二叉树所得序列的相对位置不变。具体做法有两种：①令pL直接链接到q的左（或右）孩子链域上，pR链接到p结点中序前趋结点s上（s是pL最右下的结点）；② 以p结点的直接中序前趋或后继替代p所指结点，然后再从原二叉排序树中删去该直接前趋或后继，如下图(d)、(e)、(f)所示。从图中可以看出使用①中做法，会使二叉树的深度增加，所以不如②中的做法好。

如下图所示：(红色代表要删除的节点)

图2

图3

图4

具体程序实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**************************************\
函数功能：在二叉排序树中删除节点
输入：    二叉排序树的根节点、要删除的节点的内容
输出：    二叉排序树的根节点
\**************************************/
bstnode* DelBstNode(bstnode* t,int k)
{
	bstnode *p,*q,*s,*f;
	p=t;
	q=NULL;
	while(p!=NULL)//查找要删除的内容为k的节点
	{
		if(p->key==k) break;
		q=p;
		if(p->key<k)
			p=p->rchild;
		else
			p=p->lchild;
	}
	if(p==NULL)
	{
		printf("\n没有找到该节点\n");
		return t;
	}
    if(p->lchild==NULL)   /* p所指结点的左子树为空 */
    { 
	   if (q==NULL) 
		   t=p->rchild;       /* p所指结点是原二叉排序树的根 */
       else if (q->lchild==p)   /* p所指结点是*q的左孩子 */
  		   q->lchild=p->rchild;
	   else  q->rchild=p->rchild;  	/* 将p所指右子树链接到*q的右指针域上 */
       free(p);                      	   /* 释放被删结点 */
  	}	
   else     /* p所指结点有左子树时，则按图12.21(e)方法进行 */
    {
		f=p;  s=p->lchild; 
		while(s->rchild!=NULL )   /* 在pL中查找最右下结点 */
        {
		  f=s; 
		  s=s->rchild;
		}
		if ( f==p ) 
			  f->lchild=s->lchild;    /* 将s所指结点的左子树链接到*f上*/
		else f->rchild=s->lchild; 
		p->key=s->key;              /* 将s所指结点的值赋给*p */
		
		free(s);   				/* 释放被删结点 */
    }
   return  t; 
}

一个完整实例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include<stdio.h>
#include<malloc.h>

#define maxsize 20

typedef struct node
{
	int key;
	struct node*lchild,*rchild;
}bstnode;//二叉排序树的节点结构

bstnode* InsertBst(bstnode* t,bstnode* s);//二叉排序树的插入
bstnode* CreatBst(int* arrayA,int n);//二叉排序树的创建
void Layer(bstnode *p);//二叉排序树的广度优先遍历
bstnode* DelBstNode(bstnode* t,int k);//二叉排序树的删除

void main()
{
	int arrayA[9]={-1,5,2,4,3,1,6,7,8};//第一个节点没有用于存储数据，是为了方便计算
	int n=sizeof(arrayA)/sizeof(int);

	bstnode *head=NULL;//初始化指向链表的头指针
	head=CreatBst(arrayA,n);
	printf("创建的二叉排序树的广度优先遍历为：\n");
    Layer(head);
	printf("\n删除内容为5后的二叉排序树的广度优先遍历为：");
	head=DelBstNode(head,5);
	printf("\n");
	Layer(head);
}
/**************************************\
函数功能：向二叉排序树中插入节点
输入：    二叉排序树的根节点、要插入的节点
输出：    二叉排序树的根节点
\**************************************/
bstnode* InsertBst(bstnode* t,bstnode* s)
{
	bstnode *f,*p;
	p=t;
	while(p!=NULL)
	{
		f=p;
	
		if(s->key<=p->key)
			p=p->lchild;
		else
			p=p->rchild;
	}
	if(t==NULL)
		return s;
	if(s->key<f->key)
		f->lchild=s;
	else
		f->rchild=s;
	return t;

}

/**************************************\
函数功能：创建二叉排序树
输入：    原始数组
输出：    二叉排序树的根节点
\**************************************/
bstnode* CreatBst(int* arrayA,int n)
{
	bstnode *t,*s;
	t=NULL;
	for(int i=1;i<n;i++)
	{
		s=(bstnode*)malloc(sizeof(bstnode));
		s->key=arrayA[i];//从arrayA[1]开始
		s->lchild=s->rchild=NULL;
		t=InsertBst(t,s);//调用插入函数
	}
	return t;
}

/**************************************\
函数功能：广度优先遍历二叉排序树
输入：    二叉排序树的根节点
输出：    无
\**************************************/
void Layer(bstnode *p)
{
	bstnode* queue[maxsize];//queue数组用于存储节点地址
	bstnode* s;
	int rear=0;  //队列尾指针
	int front=0; //队列头指针

	if(p!=NULL)//输入的树不为空
	{
		rear=1; //初始化
		front=0;
		queue[rear]=p;
		while(front<rear)//判断队列是否为空
		{
			front++;
			s=queue[front];
			printf("%d ",s->key);
			if(s->lchild!=NULL) //存储左右子节点
			{
				rear++;
				queue[rear]=s->lchild;
			}
			if(s->rchild!=NULL)
			{
				rear++;
				queue[rear]=s->rchild;
			}
		}
	}
}

/**************************************\
函数功能：在二叉排序树中删除节点
输入：    二叉排序树的根节点、要删除的节点的内容
输出：    二叉排序树的根节点
\**************************************/
bstnode* DelBstNode(bstnode* t,int k)
{
	bstnode *p,*q,*s,*f;
	p=t;
	q=NULL;
	while(p!=NULL)//查找要删除的内容为k的节点
	{
		if(p->key==k) break;
		q=p;
		if(p->key<k)
			p=p->rchild;
		else
			p=p->lchild;
	}
	if(p==NULL)
	{
		printf("\n没有找到该节点\n");
		return t;
	}
    if(p->lchild==NULL)   /* p所指结点的左子树为空 */
    { 
	   if (q==NULL) 
		   t=p->rchild;       /* p所指结点是原二叉排序树的根 */
       else if (q->lchild==p)   /* p所指结点是*q的左孩子 */
  		   q->lchild=p->rchild;
	   else  q->rchild=p->rchild;  	/* 将p所指右子树链接到*q的右指针域上 */
       free(p);                      	   /* 释放被删结点 */
  	}	
   else     /* p所指结点有左子树时，则按图12.21(e)方法进行 */
    {
		f=p;  s=p->lchild; 
		while(s->rchild!=NULL )   /* 在pL中查找最右下结点 */
        {
		  f=s; 
		  s=s->rchild;
		}
		if ( f==p ) 
			  f->lchild=s->lchild;    /* 将s所指结点的左子树链接到*f上*/
		else f->rchild=s->lchild; 
		p->key=s->key;              /* 将s所指结点的值赋给*p */
		
		free(s);   				/* 释放被删结点 */
    }
   return  t; 
}

参考文献：《计算机软件技术基础》 刘彦明 荣政 编 、《 算法导论》

坚持原创技术分享，您的支持将鼓励我继续创作！